package algorithm.sort.child;

import algorithm.sort.basic.Sort;

/**
 * 项目名称: god
 * 包 名 称: algorithm.sort.child
 * 类 名 称: InsertSort2
 * 类 描 述: TODO
 * 创建时间: 2020/6/23 10:05 下午
 * 创 建 人: Justice
 */
public class InsertSort2<T extends Comparable<T>> extends Sort<T> {
    @Override
    protected void sort() {
        for (int begin = 1; begin < array.length; begin++) {
            int current = begin;
            // 将待插入元素备份
            T t = array[begin];
            while (current > 0 && cmp(t, array[current - 1]) < 0) {
                // 头部有序数据中比待插入元素大的，都朝尾部方向挪动1个位置
                array[current] = array[current - 1];
                current--;
            }
            // 将待插入元素放到最终的合适位置
            array[current] = t;
        }
    }
}
